package demo_leetcode_day;

/*
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
提示：
1 <= N <= 1000
*/

import java.util.HashMap;
import java.util.Map;

public class demo_20200724 {
    public static void main(String[] args) {
        System.out.println(new Solution().divisorGame(377));
    }

    // 题目解析爱丽丝和鲍勃的胜利其实就是奇数的胜利和偶数的胜利
    static class Solution {
        Map<Integer, Boolean> retMap = new HashMap<>();
        public boolean divisorGame(int N) {
            if (N == 0) return false;
            if (N == 1) return false;
            if (N == 2) return true;
            if (N == 3) return false;
            // 使用map缓存
            if(retMap.containsKey(N)){
                return retMap.get(N);
            }

            // 遍历，取可能的除数
            for (int x = N / 2; x >= 1; x--) {
                if (N % x != 0) continue;
                // 使用N-x进行查询，其值不存在成功时，判断爱丽斯的胜利
                if (!divisorGame(N - x)) {
                    if(!retMap.containsKey(N)){
                        retMap.put(N, true);
                    }
                    return true;
                }
            }
            if(!retMap.containsKey(N)){
                retMap.put(N, false);
            }
            return false;
        }
    }
}
